#include <iostream>
#include <cstdlib>

using namespace std;
const int maxn=20;

/*
问题描述:
n个人站成一排，从左向右编号为1~你，现在从左到右进行报数，数到 1 的人出列,数到2的人站到队伍最后
反复进行，直到剩下最后一人，给出出列的顺序
*/
//求解的数据类型：环形队列
typedef struct
{
    int data[maxn];
    int rear,front;
} sqQuene;
void initQuene(sqQuene *&q)
{
    q = (sqQuene *)malloc(sizeof(sqQuene));
    q->front = q->rear = 0;  //环形队列
}
//队列判空
bool QueueEmpty(sqQuene *q)
{
    return q->front == q->rear;
}
//进队操作
bool enQueue(sqQuene *&q, int e)
{
    if((q->rear+1)%maxn == q->front)  //队满，无法入队
        return false;
    q->rear=(q->rear+1)%maxn;
    q->data[q->rear] = e;
    return true;
}
//出队操作
bool deQueue(sqQuene *&q, int &e)
{
    if(q->rear == q->front) //队空
        return false;
    q->front = (q->front+1)%maxn;
    e = q->data[q->front];
    return true;
}

void number(int n)//报数
{
    int i;
    int e;
    sqQuene *q;  //环形队列指针
    initQuene(q);  //初始化环形队列
    for(i=1;i<=n;i++)
        enQueue(q, i);//构建初始化队列
    cout<<"报数的顺序";
    while(!QueueEmpty(q))
    {
        deQueue(q,e);  //出队一个元素
        cout<<e;
        if(!QueueEmpty(q))
        {
            deQueue(q,e);  //出队第二个元素
            enQueue(q,e);  //将刚出队的元素入队
        }
    }
}

int main()
{
    int i;
    int n=8;
    cout<<"初始化序列:\n";
    for(i==1;i<=n;i++)
        cout<<i<<' ';
    cout<<'\n';
    number(n);
    return 0;
}

